package com.dyz.swordFingerOffer;

/**
 * @author: daiyizheng
 * @date: 2021/6/5 11:39
 * @description:
 */
public class VerifySquenceOfBST32 {
    public static void main(String[] args) {
        int[] arr = new int[]{4,8,6,12,16,14,10};
        new VerifySquenceOfBST32().VerifySquenceOfBST(arr);
    }
    public boolean VerifySquenceOfBST(int [] sequence) {
        //思路构建二叉搜索树
        // 后续遍历
        if(sequence==null|| sequence.length==0){
            return false;
        }

        int size = sequence.length;
        int left = 0;
        int right = size-1;
        return dfs(sequence, left,right);


    }

    public boolean dfs(int [] sequence, int left, int right){
        if(left>=right){
            return true;
        }

        int k = left;
        int root_val = sequence[right];
        while(k<right && sequence[k]<root_val){
            k++;
        }
        //判断右子树的节点是否都大于根节点
        for(int i = k; i<right;i++){
            if(sequence[i]<root_val){
                return false;
            }
        }
        return dfs(sequence, left, k-1) && dfs(sequence,k, right-1);
    }
}
